《剑指offer》 29. 顺时针打印矩阵

note： 虽然是简单题，但是挺麻烦，尤其是在（好久）没做过的情况下，建议记住方法二的第二种写法，更简洁易懂一点。

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

方法一 模拟

思路

通过方向数组模拟遍历路径，以便进行顺时针旋转。同时搭配一个标识是否访问过的数组，防止重复访问。

首先是向右、向下、向左和向上的方向数组：

static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组

使用方向索引directionIndex来决定选用那个方向数组。

然后引入理论下标nextRow和nextColumn，来计算方向不改变时，下一个要访问的元素的下标。

判断理论下标是否合法，不合法的情况有两个，其一是数组越界，其二是访问的元素已经访问过了。

当理论下标不合法时，变换方向索引到顺时针的下个方向。

然后更新下标为真实的合法下标。

代码

class Solution {
private:
    static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 超出情况
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }   
        
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(columns));  // 标识数组
        int total = rows * columns; 
        vector<int> order(total);

        int row = 0, column = 0;
        int directionIndex = 0; // 方向索引
        for (int i = 0; i < total; i++) {       // 所有元素都访问到
            order[i] = matrix[row][column];
            visited[row][column] = true;    // 标记标识数组
            // 下一个访问的数组元素下标理论值
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            // 理论值是否不合法，不合法顺时针转换方向
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            // 下标的真实变换
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
};

复杂度分析

• 时间复杂度$O(mn)$。要遍历所有的元素，m n分别为矩阵的长和宽
• 空间复杂度$O(mn)$。需要一个和矩阵相同大小的二维数组作为标记数组。

方法二 按层遍历

思路

方法一的思路是矩阵不变，标记已访问的元素避免重复访问。

事实上，我们也可以不断改变矩阵的边界，达到一层层缩小矩阵的边界的效果，按层遍历，从而可以得到顺时针遍历同样的效果。

我们用四个变量l r t b代表当前层的矩阵的左右上下边界

在左边界大于右边界、上边界大于下边界之前，我们重复四个步骤

• 从左到右访问上边界那一排元素
• 从上到下访问右边界那一列元素
• 如果左上边界都小于右下边界，那么我们
  • 从右到左访问下边界这一排元素
  • 从下到上访问左边界这一排元素
• 更改边界，左边界上边界自增，右边界下边界自减。

代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0 || matrix[0].size()==0){
            return {};
        }

        int m = matrix.size(),n=matrix[0].size();

        int l=0,r=n-1,t=0,b=m-1;  
        vector<int> ans;
        while(l<=r && t<=b){
            for(int i=l;i<=r;i++){
                ans.push_back(matrix[t][i]);
            }
            for(int i=t+1;i<=b;i++){
                ans.push_back(matrix[i][r]);
            }
            if (l < r && t < b){
                for(int i=r-1;i>l;i--){
                    ans.push_back(matrix[b][i]);
                }
                for(int i=b;i>t;i--){
                    ans.push_back(matrix[i][l]);
                }
            }
            l++;
            r--;
            t++;
            b--;
        }
        return ans;
    }
};

如果较难理解，还有一种写法，即在每排每列访问完后，立刻进行边界的缩小，并判断是否合法，如果不合法则说明已经遍历完毕，可以直接结束

class Solution 
{
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        if (matrix.empty()) return {};
        vector<int> res;
        int l = 0;                      //左边界
        int r = matrix[0].size() - 1;   //右边界
        int t = 0;                      //上边界
        int b = matrix.size() - 1;      //下边界
        while (true)
        {
            //left -> right
            for (int i = l; i <= r; i++) res.push_back(matrix[t][i]);
            if (++t > b) break;
            //top -> bottom
            for (int i = t; i <= b; i++) res.push_back(matrix[i][r]);
            if (--r < l) break;
            //right -> left
            for (int i = r; i >= l; i--) res.push_back(matrix[b][i]);
            if (--b < t) break;
            //bottom -> top
            for (int i = b; i >= t; i--) res.push_back(matrix[i][l]);
            if (++l > r) break;
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(mn)$。要访问矩阵种所有的元素
• 空间复杂度：$O(1)$。不需要标记数组。

文章目录

1. 题目描述
2. 方法一 模拟
   1. 思路
   2. 代码
   3. 复杂度分析
3. 方法二 按层遍历
   1. 思路
   2. 代码
   3. 复杂度分析

原文链接: https://zijian.wang/2021/07/19/29. 顺时针打印矩阵/

版权声明: 转载请注明出处.